הרובוט שלמד לעוף - אלגוריתמים גנטיים 

חוקרים בשוודיה הצליחו לגרום לרובוט ללמוד בעצמו לעוף. החוקרים השתמשו באלגוריתם גנטי כדי לאפשר לרובוט ללמוד את הדרך הטובה ביותר להתרומם, ע?י ניסוי וטעיה.

אלגוריתמים גנטיים הם אלגוריתמים שנוצרו כדי להתמודד עם מצבים בהם יש כמות גדולה של משתנים, ואלגוריתמים אלו נועדו למצא פתרון אופטימלי, או קרוב לאופטימלי, בזמן סביר.
כדי להסביר את דרך הפעולה של האלגוריתמים האלו אני אשתמש בדוגמא אמיתית, ויחסית קלה להבנה ופישוט: בארץ פועלת חברה המשתמשת באלגוריתמים גנטיים כדי למצא את הדרך לכסות שטח גדול ככל האפשר, ברשת סלולרית, תוך שימת דגש על עלות מינימלית. אני לא מכיר את האלגוריתמים בהם הם משתמשים (למעשה אני לא זוכר אפילו את שם החברה כרגע) אבל אני אנסה לפשט את הבעיה הזו כדי להסביר את העקרונות.

האלגוריתמים הגנטיים עובדים עפ?י העקרון הבא:
1)המתכנתים מגדירים בעיה, ודרך לתת ציון לפתרונות שלה.
בדוגמא שנתתי, הבעיה היא השגת הכיסוי המלא לאיזור הנבחר. הציון יהיה ביחס הפוך לכמות האנטנות שצריך (ככל שצריך פחות אנטנות לכיסוי מלא, הציון גבוה יותר) ועפ?י כמות השטח המכוסה.
2)א) בהתחלת הפעולה (?דור ראשון?) נבחרים מספר מסוים של פתרונות לבעיה (יכולים להיות גם אקראיים).
בדוגמא שלנו, נתון של הבעיה הוא שאפשר בשבעה אנטנות לכסות את כל האיזור. אנו יכולים להגדיר לתוכנה לא לעלות מעל 7 אנטנות, ולהגדיר פתרונות אקראיים (המחשב יבחר כמות אנטנות אקראית, עד 7 אנטנות, ומיקום אקראי לכל אנטנה, בשטח המוגדר).
ב) השלב הבא הוא בדיקת כל אחד מהפתרונות (מתן ציונים).
בדוגמא, זה יכל להיות בדיקה אם באמת בכמות ובמיקום הנוכחי של האנטנות כל השטח מכוסה (וכמה אנטנות צריך), ומתן ציון מספרי לכל פתרון.
ג) השלב השלישי הוא לקחת זוגות מהפתרונות המוצלחים יותר (שוב, עפ?י הציון) ו?לזווג? אותם: להחליף חלקים (בלוקים) ביניהם באופן אקראי, ולפעמים גם להכניס גורם אקראי לתוצאה.
לדוגמא, מתוך 100 פתרונות ראשוניים ניקח את 20 הפתרונות הטובים. את ה-20 האלו ?נזווג?: נקח חלק מהאנטנות מאחד הפתרונות בזוג אחד של הדור הראשון, ואת השאר מהפתרון השני מאותו הזוג, לדוגמא. ואחר כך נוסיף גורם אקראי (חלק מהאנטנות יזוזו טיפה), ובסה?כ, ניצור שוב 100 פתרונות ל?דור השני?.
ד) בהמשך חוזרים על שלבים א,ב, ו-ג? כדי ליצור דור שלישי, רביעי ו... עד כמה שצריך.

הערה: בהסבר פישטתי במקצת (אבל באמת קצת) את התהליך. לדוגמא, לא לוקחים את הפתרונות עם הציונים הכי טובים, אלא מגרילים פתרונות לשלב הבא, כשלכל פתרון, הסיכוי לעבור לשלב הבא תלוי בציון.

ועכשיו בחזרה לרובוט:
הבעיה שהגדירו לרובוט היא התעופה. הדרך למדוד את התוצאה (לתת ציון) היא עפ?י הגובה אליו הגיע הרובוט (נמדד ע?י חוט שחובר אליו).
בדורות הראשונים התוכנה, כצפוי, סתם ?הפעילה? את המנועים בצורה אקראית. הרובוט סתם עשה פעולות ללא שום הגיון. במשך הזמן התפתחו תנועות שהרימו את הרובוט לגובה גבוה יותר ( = ציון גבוה יותר), לדוגמא ?לעמוד על הכנפיים? אך עדיין לא היה מדובר בתעופה (אך כמובן, זו היתה התקדמות). לאחר שלש שעות, הרובוט עזב את הטכניקות האלה לטובת נפנוף בכנפיים? הפעולה שהרובוט מצא כאופטימלית היא לסובב את הכנפיים (כך שיוכלו לעלות עם חיכוך אויר מינימלי),להרים את הכנפיים, לסובב שוב את הכנפיים ב-90 מעלות, ולהוריד אותם. ובמהירות.

הרובוט, למרות שהצליח להשיג עילוי מסויים, לא מצוייד במנוע חזק מספיק כדי שיוכל להתחיל להתעופף בחדר, וגם אינו יודע לנווט (אולי ילמד בעתיד?) אבל זו בהחלט התחלה. והתחלה מרשימה מאד לדעתי.

עוד על הרובוט תוכלו לקרא בכתבה של ה- New ,Scientist בכתובת http://www.newscientist.com/news/news.jsp?id=ns99992673

המאמר נכתב במקור באוגוסט 2002